package huawei_nowcoder;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.Scanner;

/**
 * @Description: Sudoku-Java
 * @Date: 2020/4/26
 * @Author: 许群星
 */
public class Sudoku {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            //输入
            int[][] grid=new int[9][9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    grid[i][j]=sc.nextInt();
                }
            }
            //处理
            handle(grid,0,0);
            //输出
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (j == 8) {
                        System.out.println(grid[i][j]);
                    } else {
                        System.out.print(grid[i][j]+" ");
                    }
                }
            }
        }
    }

    //处理数独
    //想法：找到包含0最少的一行或者一列，把当前行或者当前列中的不是的数填写
    private static boolean handle(int[][] grid,int i,int j) {
        if (i > 8) {
            return true;
        }
        if (grid[i][j] != 0) {
            //未到行尾，求解同行下一个
            if (j < 8 && handle(grid, i, j + 1)) {
                return true;
            } else if (j >= 8 && handle(grid, i + 1, 0)) {
                //已到行尾，求解下一行第一个
                return true;
            }
        } else {
            for (int k = 1; k <= 9; k++) {
                if (check(grid, i, j, k)) {
                    grid[i][j]=k;
                    if (j < 8 && handle(grid, i, j + 1)) {
                        return true;
                    } else if (j >= 8 && handle(grid, i + 1, 0)) {
                        return true;
                    }
                    grid[i][j]=0;//回溯
                }
            }
        }
        return false;
    }

    //总体检查
    private static boolean check(int[][] grid, int i, int j, int num) {
        if (check_row(grid, i, j, num) && check_col(grid, i, j, num) && check_block(grid, i, j, num)) {
            return true;
        }
        return false;
    }
    //检查行
    private static boolean check_row(int[][] grid, int i, int j, int num){
        for (int k = 0; k < 9; k++) {
            if (grid[i][k]==num) {
                return false;
            }
        }
        return true;
    }
    //检查列
    private static boolean check_col(int[][] grid, int i, int j, int num){
        for (int k = 0; k < 9; k++) {
            if (grid[k][j]==num) {
                return false;
            }
        }
        return true;
    }
    //检查块
    private static boolean check_block(int[][] grid, int i, int j, int num){
        int row_from=i/3*3;
        int row_to=row_from+2;
        int col_from=j/3*3;
        int col_to=col_from+2;

        for (int k = row_from ; k < row_to; k++) {
            for (int l = col_from; l <col_to ; l++) {
                if (grid[k][l] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}
/*
题目描述
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，
并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。
输入：
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出：
完整的9X9盘面数组

输入描述:
包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述:
完整的9X9盘面数组

示例1
输入
复制
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1
输出
复制
5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1
 */